import java.util.Arrays;

class Solution {
    //解法1：时间复杂度与空间复杂度均为 o（n）
    public int findRepeatNumber(int[] nums) {
        int [] arr = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            arr[nums[i]]++;
            if (arr[nums[i]] > 1) return i;
        }

        return -1;
    }
    //解法2:效率不如1
    public int findRepeatNumber2(int[] nums) {
        Arrays.sort(nums);
        int i = 0;
        for (i = 0; i < nums.length; i++) {
            if (nums[i] == nums[i+1]) break;
        }
        return nums[i];
    }
    //解法3：
    public int findRepeatNumber3(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            while (nums[i] != i) {
                if (nums[i] == nums[nums[i]]) {
                    return nums[i];
                }
                int temp = nums[nums[i]];
                nums[nums[i]] = nums[i];
                nums[i] = temp;
            }
        }
        return -1;
    }
}